package com.zs.letcode.illustration_of_algorithm;

/**
 * 剑指 Offer 53 - I. 在排序数组中查找数字 I
 * 统计一个数字在排序数组中出现的次数。
 * <p>
 *
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * 示例2:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 *
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 105
 * -109<= nums[i]<= 109
 * nums是一个非递减数组
 * -109<= target<= 109
 *
 * <p>
 * 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 * <p>
 * 相关标签
 * 数组
 * 二分查找
 * <p>
 * Java
 * <p>
 * <p>
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5874p1/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/26 07:56
 */
public class Chapter53 {
    public static void main(String[] args) {

    }

    private class Solution {
        public int search(int[] nums, int target) {
            int length = nums.length;
            // 搜索右边界 right
            int i = 0, j = length - 1;
            while (i <= j) {
                int mid = (i + j) / 2;
                if (nums[mid] <= target) i = mid + 1;
                else j = mid - 1;
            }
            int right = i;
            // 若数组中无 target ，则提前返回
            if (j >= 0 && nums[j] != target) return 0;
            // 搜索左边界 right
            i = 0;
            j = length - 1;
            while (i <= j) {
                int mid = (i + j) / 2;
                if (nums[mid] < target) i = mid + 1;
                else j = mid - 1;
            }
            int left = j;
            return right - left - 1;
        }

        public int search1(int[] nums, int target) {
            return helper(nums, target) - helper(nums, target - 1);
        }

        private int helper(int[] nums, int tar) {
            int i = 0, j = nums.length - 1;
            while (i <= j) {
                int m = (i + j) / 2;
                if (nums[m] <= tar) i = m + 1;
                else j = m - 1;
            }
            return i;
        }
    }

    public int search2(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length &&
                nums[leftIdx] == target && nums[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        }
        return 0;
    }

    private int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
